class Node {
  pre;
  next;
  key;
  value;

  constructor(key, value) {
    this.key = key;
    this.value = value
  }
}

class LRUCache {
  head;
  end;
  limit;//缓存存储上限

  hashMap;

  constructor(limit) {
    this.limit = limit;
    this.hashMap = new Map()
  }

  get(key) {
    const node = this.hashMap.get(key);
    if (node == null) {
      return null;
    }
    this.refreshNode(node);
    return node.value;
  }

  put(key, value) {
    const node = this.hashMap.get(key);
    if (node == null) {
      //如果key不存在，插入key-value
      if (this.hashMap.size >= this.limit) {
        const oldKey = this.removeNode(this.head);
        this.hashMap.delete(oldKey);
      }
      const node = new Node(key, value);
      this.addNode(node);
      this.hashMap.set(key, node);
    } else {
      //如果key存在，刷新key-value
      node.value = value;
      this.refreshNode(node);
    }
  }

  remove(key) {
    const node = this.hashMap.get(key);
    if (node == null) {
      return;
    }
    this.removeNode(node);
    this.hashMap.remove(key);
  }

  refreshNode(node) {
    //如果访问的是尾节点，无需移动节点
    if (node === this.end) {
      return;
    }
    //移除节点
    this.removeNode(node);
    //重新插入节点
    this.addNode(node);
  }

  /**
   * 删除节点
   * @param  node 要删除的节点
   */
  removeNode(node) {
    if (node == this.head && node == this.end) {
      //移除唯一的节点
      this.head = null;
      this.end = null;
    } else if (node == this.end) {
      //移除尾节点
      this.end = this.end.pre;
      this.end.next = null;
    } else if (node == this.head) {
      //移除头节点
      this.head = this.head.next;
      this.head.pre = null;
    } else {
      //移除中间节点
      node.pre.next = node.next;
      node.next.pre = node.pre;
    }
    return node.key;
  }

  /**
   * 尾部插入节点
   * @param  node 要插入的节点
   */
  addNode(node) {
    if (this.end != null) {
      this.end.next = node;
      node.pre = this.end;
      node.next = null;
    }
    this.end = node;
    if (this.head == null) {
      this.head = node;
    }
  }
}
const run = ()=>{
  const lruCache = new LRUCache(5);
  lruCache.put("001", "用户1信息");
  lruCache.put("002", "用户2信息");
  lruCache.put("003", "用户3信息");
  lruCache.put("004", "用户4信息");
  lruCache.put("005", "用户5信息");
  lruCache.get("002");
  lruCache.put("004", "用户4信息更新");
  lruCache.put("006", "用户6信息");
  console.log(lruCache.get("001"));
  console.log(lruCache.get("006"));
};
run();